package Algorithms;

import java.util.Scanner;

public class mergesortlow {
	public static void merge(Comparable[]a,int lo,int mid,int hi,Comparable[]aux) {
		
		int i=lo,j=mid+1;
		for(int k=lo;k<=hi;k++)aux[k]=a[k];
		for(int k=lo;k<=hi;k++) {
			if(i>mid) {a[k]=aux[j++];}
			else if(j>hi) {a[k]=aux[i++];}
			else if(less(aux[i], aux[j])) {a[k]=aux[i++];}
			else {a[k]=aux[j++];}
		}
	}
	public static void sort(Comparable[]a) {
		Comparable[]aux=new Comparable[a.length];
		int N=a.length;
		for(int sz=1;sz<N;sz=sz+sz) {
			for(int lo=0;lo<N-sz;lo+=sz+sz) {
				merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1),aux);
			}
		}
	}
	private static boolean less(Comparable v,Comparable w) {
		return v.compareTo(w)<0;
	}
	public static boolean isSorted(Comparable[]a,int lo,int hi) {
		for(int i=lo;i<=hi;i++) {
			if(less(a[i], a[i+1]))return false;
		}
		return true;
	}
	public static void show(Comparable[] a) {
		for(int i=0;i<a.length;i++) {
			System.out.print(a[i]+" ");
		}
		System.out.println("");
	}
	public static void main(String[]args) {
		Scanner scanner=new Scanner(System.in);
		String[]a=new String[10];
		for(int i=0;i<10;i++) {
			a[i]=scanner.next();
		}
		show(a);
		sort(a);
		show(a);
	}
}
